[% setvar title docs/pdds/pdd14_bignum.pod - Big Numbers %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='NAME'></a><h1>NAME</h1>
<p>docs/pdds/pdd14_bignum.pod - Big Numbers</p>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>This document describes the big number library, the functionality it
provides and some internal details of interest to people making use of
the library.  Some of the areas in which the big number library meet
with the rest of Parrot are also discussed.</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>The big number library provides Parrot with both a collection of
(nearly) infinite precision numeric types and an implementation of an
extended decimal arithmetic (EDA).</p>
<a name='Why decimal arithmetic?'></a><h2>Why decimal arithmetic?</h2>
<p>There are benefits in using the big number library to provide both
values of effectively unlimited precision and a defined arithmetic,
complete with rounding and exceptional conditions, for values which
are otherwise easily represented using standard low-level types.  Both
require the same range of operations but differ in the environment
under which those operations occur.  The effort required to produce a
library which implements a decimal arithmetic is not much greater than
that needed to provide a base-2 big number library.  It is true that
some trade-off in both space and speed is made but given the nature of
dynamic languages, this should not present too great a burden.</p>
<a name='Numeric types provided'></a><h2>Numeric types provided</h2>
<p>The bignumber library provides the following data types to Parrot:</p>
<ul>
<li><a name='Big integers (BigInt)'></a>Big integers (BigInt)</li>
<p>Whole numbers with no limits on their size.</p>
<li><a name='Big floats (BigNum)'></a>Big floats (BigNum)</li>
<p>Numbers with decimal fractional parts, again with no limit on size.</p>
<li><a name='Big floats with fixed fractional parts'></a>Big floats with fixed fractional parts</li>
<p>Numbers with a fixed maximum number of digits in their fractional
part, again with no limit on size.</p>
</ul>
<p>The library implements these different forms of number using the same
internal representation, and differentiates between them only when
performing rounding operations.  A number has the following abstract
form:</p>
<pre> [ sign, string of digits, exponent ]</pre>
<p>If sign is zero, the number is positive, if equal to one, the number is
negative.  The number has the value</p>
<pre> sign, string of digits * 10 ** exponent</pre>
<p>A big integer must always have a non-negative exponent, a big float
may have any exponent and a float with a fixed fractional part will
have an exponent greater than a given (negative) number.  These limits
are not attached to a numeric value, but instead are enforced by
giving any operation involving the numbers a <i>context</i>.</p>
<p>In general, Parrot functions will not need to care about what the
bignum objects are or do, they should merely be used as arguments to
big number functions, the objects will be managed by Parrot's garbage
collection in a similar manner to strings.</p>
<a name='Special Values'></a><h2>Special Values</h2>
<p>Additionally the library provides special values, which represent the
result of otherwise undefined operations (division by zero, for
instance).  +Infinity, -Infinity and both quiet and signalling Not a
Number (NaN) are available.  In general, the result of an operation
with at least one argument which is NaN will be NaN, if the argument
is a signalling NaN, an exception will also be raised.  See the EDA
for full details.</p>
<a name='Context'></a><h2>Context</h2>
<p>All operations occur within a defined context.  This tells the
operations how they should be treating their arguments, what sort of
rounding to perform and what to do if information is lost through
rounding.</p>
<p>The context provides the environment in which an operation occurs,
in particular the following options are available:</p>
<ul>
<li><a name='precision'></a>precision</li>
<p>A positive <i>precision</i> indicates that big floats are to be used,
these cannot have more than <i>precision</i> digits in their coefficient
before or after any operation.  Arguments to operations with more than
<i>precision</i> digits will be truncated and rounded appropriately and
results of operations will not have more than <i>precision</i> digits in
their coefficients, with any extra digits accumulated during the
calculation of the operation being truncated and rounded as required.</p>
<p>A <i>precision</i> of zero indicates that integer operations are to be
performed.  Arguments to operations are rounded so that they have no
fractional part, and the result of all operations will be rounded to
be integers.</p>
<p>A negative value of <i>precision</i> indicates that a fixed number of
fractional digits are to be provided, with arguments and results being
truncated after those digits.</p>
<p>With non-positive values of <i>precision</i> the total number of digits in
the coefficient is limited only by available memory.</p>
<li><a name='rounding'></a>rounding</li>
<p>The rounding part of the context defines the rounding algorithm which
is to be applied when truncating digits from a number's coefficient.
The available rounding forms are outlined below.</p>
<li><a name='traps and flags'></a>traps and flags</li>
<p>The <i>traps</i> part of the context defines how exceptions are raised by
the library.  Seven distinct classes of error can occur, if the
corresponding trap is set (enabled) then an exception is raised by the
library (and dispatched to Parrot) otherwise execution continues with
the exception class being recorded in flags.  For more details see the
extended decimal arithmetic standard.</p>
</ul>
<p>It is therefore the current <i>context</i> which determines which numeric
type is being considered during a particular operation, this makes it
easy to upgrade from one numeric form to another, and also allows for
considerable code-reuse within the library.</p>
<a name='Exception Classes'></a><h2>Exception Classes</h2>
<p>The following exception classes are defined:</p>
<ul>
<li><a name='Lost Digits'></a>Lost Digits</li>
<p>Non-zero digits have been removed from an argument to a function
during rounding before the operation.</p>
<li><a name='Division By Zero'></a>Division By Zero</li>
<p>Division by zero was attempted.</p>
<li><a name='Inexact'></a>Inexact</li>
<p>Because arguments were rounded, or because the result of an operation
has lost significant digits, the result is inexact.</p>
<li><a name='Invalid Operation'></a>Invalid Operation</li>
<p>An invalid operation was attempted, for instance a sNaN was provided
as an argument to a function.  This also covers recoverable errors
like 0/0, which signals Invalid Operation and can return NaN.</p>
<li><a name='Overflow'></a>Overflow</li>
<p>The exponent of a number has overflowed.</p>
<li><a name='Rounded'></a>Rounded</li>
<p>An argument has been rounded.</p>
<li><a name='Underflow'></a>Underflow</li>
<p>The exponent of a number has underflowed.</p>
</ul>
<a name='Rounding'></a><h2>Rounding</h2>
<p>The rounding part of the context defines the rounding algorithm to be
used, the following are provided (examples assume a precision of 5):</p>
<ul>
<li><a name='Round down'></a>Round down</li>
<p>Any unwanted digits are simply truncated from the coefficient.  This
rounds towards zero.</p>
<pre> [0, 1234567, 10] =&gt; [0, 12345, 12]</pre>
<li><a name='Round half up'></a>Round half up</li>
<p>The first lost digit is examined, if this is in the range 0-4, the
coefficient is truncated directly, if in the range 5-9, one is added
to the final digit of the coefficient.  If this leads to a coefficient
with more than <i>precision</i> digits, the number is rounded again,
removing the trailing zero.  This is essentially rounding to nearest.</p>
<pre> [0, 1234567, 10] =&gt; [0, 12346, 12]
 [0, 1234549, 10] =&gt; [0, 12345, 12]
 [0, 9999950, 10] =&gt; [0, 10000, 13]</pre>
<li><a name='Round half even'></a>Round half even</li>
<p>The first lost digit is examined, if it lies in the range 0-4, the
coefficient is truncated directly, if in the range 6-9, the
coefficient is rounded up.  If the first lost digit is equal to 5, and
the remaining lost digits in the coefficient are non-zero, the number
is also rounded up.  If the lost digits are equal to exactly half, the
number is rounded up if the least significant retained digit is odd,
and rounded down if it is even.</p>
<li><a name='Round Floor'></a>Round Floor</li>
<p>If the digits to be discarded are non zero, and the number is negative,
the coefficient is rounded up, otherwise it remains the same.</p>
<p>This is rounding towards -Infinity.</p>
<li><a name='Round Ceiling'></a>Round Ceiling</li>
<p>If the digits to be discarded are non zero, and the number is positive,
the coefficient is rounded up, otherwise it remains the same.</p>
<p>This is rounding towards +Infinity.</p>
</ul>
<a name='Operations'></a><h2>Operations</h2>
<p>The following operations are provided by the library, they function
exactly as those described in the Standard Decimal Arithmetic (SDA)
(see references below) with some extension to cope with integer and
fixed fractional part numbers.  Only the deviations are outlined here.</p>
<p>In all cases, the sequence of rounding and promotion to zero outlined
by the SDA are followed, even where the context implies integer
operations.</p>
<ul>
<li><a name='Addition, Subtraction'></a>Addition, Subtraction</li>
<li><a name='Multiplication'></a>Multiplication</li>
<li><a name='Division'></a>Division</li>
<p>Under integer conditions, division is halted once the first fractional
digit is calculated, with the result then being rounded to an integer
and returned.  Under fixed-fraction conditions, one more digit than
needed is calculated, with the coefficient then being rounded and
returned.</p>
<p>If a floating point value is required, or if inexact division by a
very small number is attempted, it may be wise to follow big float
arithmetic to limit the number of digits returned.  It is safe to
chose a precision at least as big the largest number of digits
of either argument to the division function.</p>
<li><a name='Integer division, Remainder'></a>Integer division, Remainder</li>
<p>For both integer and fixed-fraction numbers, the result returned by
the remainder function will be an integer or fixed-fraction number.
The result of integer division will be an integer.</p>
<li><a name='Rounding'></a>Rounding</li>
<li><a name='Plus / Minus'></a>Plus / Minus</li>
<li><a name='Comparison'></a>Comparison</li>
<p>Comparison returns a big number which is equal to 1, 0 or -1 if the
first argument is larger, equal to or smaller than the second.  An
alternative form which returns an INTVAL is also provided.</p>
<li><a name='Rescale'></a>Rescale</li>
<li><a name='Power'></a>Power</li>
<li><a name='Square Root'></a>Square Root</li>
</ul>
<a name='Conversion to and from strings'></a><h2>Conversion to and from strings</h2>
<p>A one to one conversion between the abstract representation above and
a string is provided by the library, and acts as defined by the
standard decimal arithmetic.  Other conversation operations may also
be implemented, and these may not provide one to one mapping.</p>
<p>A pedantic error checking conversion is available within the library,
but only works with native strings.  Versions which work with Parrot
strings will also be provided, although in a separate file to the rest
of the library (they will share a common private header file).</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>Functions are provided which implement the arithmetic, conversion,
creation and destruction of big numbers by dealing with otherwise
opaque big number objects.</p>
<a name='Big number representation'></a><h2>Big number representation</h2>
<p>A big number is represented by the following structure, this is
capable of being allocated, tracked and destroyed by the Parrot
garbage collection system.</p>
<pre> typedef struct {
    BN_NIB* buffer; /* string of nibbles */
    UINTVAL nibs;   /* nibs allocated, in sizeof(BN_NIB) */
    UINTVAL flags;  /* private flags store: 001 Inf,  010 qNAN, 110 sNAN */
    INTVAL digits;  /* digits used */
    int sign;       /* sign of number, 0=&gt; positive or zero, 1 =&gt; negative */
    INTVAL expn;    /* exponent of number */
 } parrot_bignum_t;</pre>
<p>Within the library, individual decimal digits can be accessed using
macros, outside the library, access must be made via exported
functions.  BN_NIB is likely to be a UINTVAL, but this is not
essential.</p>
<p>Special values are represented by setting <i>digits</i> to zero and
setting appropriate private <i>flags</i>, using internal macros.  Infinity
has one flag field, NaN another flag field and sNaN a third.  In
general the flags should not be examined directly, even within the
module.</p>
<a name='Context'></a><h2>Context</h2>
<pre> typedef struct {
    INTVAL precision;     /* number of digs to retain */
    BN_ROUNDING rounding; /* rounding type to perform */
    BOOLVAL extended;     /* do we use extended or base semantics? */
    unsigned char flags;       /* records possible errors */
    unsigned char traps;       /* throw errors or not? */
 } parrot_bignum_context;</pre>
<p><i>BN_ROUNDING</i> is an enumeration of the possible rounding types as
described above.  <i>traps</i> is a bitmask of exception traps, 0 implies
that a trap is disabled and 1 implies it is enabled.  <i>flags</i> is a
bitmask which records exceptional conditions and has the same fields
at <i>flags</i>.</p>
<p>It is expected that language level types implement big floats using a
global floating point context which is tagged onto an interpreter
structure (and can thus be modified by called the right opcodes).
That big integers and fixed-fraction number are provided by creating a
context with an appropriate precision whenever a call into the library
is made.</p>
<a name='Exceptional Conditions'></a><h2>Exceptional Conditions</h2>
<p>When an exceptional condition is raised by the module, control is
passed to <code>BN_nonfatal()</code>, this examines the error which has occurred
and the current context to determine which class of error has occurred.
If the corresponding trap handler is not enabled, the context's flags
are updated and control is returned to the bignumber library,
otherwise the exception becomes fatal.  How this mechanism interacts
with Parrot's own is yet to be decided.</p>
<p>The possible exceptions are detailed in the extended decimal
arithmetic.</p>
<a name='Tests'></a><h1>Tests</h1>
<p>The Standard Decimal Arithmetic provides a collection of tests for
both its base and extended behaviour.  Initially it is hoped that this
library can pass all base tests, with extended tests to be included at
a later date as it is extended to cope with values such as +Inf.</p>
<a name='TODO'></a><h1>TODO</h1>
<p>Fill in the remaining functions from the EDA, verify that the test
suite still passes, integrate the library into the rest of Parrot,
provide PMC types and suitable opcodes.  Conversion to and from Parrot
strings, conversion to and from floating point types, sprintf output
of bignumbers.</p>
<a name='ATTACHMENTS'></a><h1>ATTACHMENTS</h1>
<a name='FOOTNOTES'></a><h1>FOOTNOTES</h1>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>IBM's Standard Decimal Arithmetic, with tests
<a href='http://www2.hursley.ibm.com/decimal/' target='_blank'>www2.hursley.ibm.com</a></p>
<p>Perl's Math::Big* modules.</p>
<a name='VERSION'></a><h1>VERSION</h1>
<a name='CURRENT'></a><h2>CURRENT</h2>
<pre>    Maintainer: Alex Gough (<a href='mailto:alex@earth.li'>alex@earth.li</a>)
    Class: Internals
    PDD Number: 14
    Version: $Id: pdd14_bignum.pod,v 1.5 2004/02/28 09:16:37 mikescott Exp $
    Status: Informational
    Last Modified: $Id: pdd14_bignum.pod,v 1.5 2004/02/28 09:16:37 mikescott Exp $
    PDD Format: 1
    Language: English</pre>
<a name='HISTORY'></a><h2>HISTORY</h2>
<ul>
<li><a name='version 1.1'></a>version 1.1</li>
<p>The first version is more a description of the state of the art than a
plan for the future.  The author believes this is akin to learning how
to crawl before trying to run.  Leaving the ground is considered Right
Out with attempts being left as an exercise for the interested reader.</p>
</ul>
<a name='CHANGES'></a><h1>CHANGES</h1>
<ul>
<li><a name='Version 1.0'></a>Version 1.0</li>
<p>None. First version</p>
<li><a name='Version 1.1'></a>Version 1.1</li>
<p>Special values added, exception handling updated to suit EDA,
more rounding types added, TODO added.  PDD number bagged.</p>
</ul>
</div>
